package allCellsDistOrder;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Solution {
//    static class Node{
//        int x;
//        int y;
//        int dis;
//        public Node(int x,int y,int dis){
//            this.x = x;
//            this.y = y;
//            this.dis = dis;
//        }
//    }
    public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
//        Node[] nodes = new Node[rows*cols];
//        int index = 0;
//        for (int i = 0; i < rows; i++) {
//            for (int j = 0; j < cols; j++) {
//                nodes[index++] = new Node(i,j,Math.abs(i-rCenter)+Math.abs(j-cCenter));
//            }
//        }
//        Arrays.sort(nodes, new Comparator<Node>() {
//            @Override
//            public int compare(Node o1, Node o2) {
//                return o1.dis-o2.dis;
//            }
//        });
//        int[][] ans = new int[rows*cols][2];
//        for (int i = 0; i < nodes.length; i++) {
//            ans[i][0] = nodes[i].x;
//            ans[i][1] = nodes[i].y;
//        }
//        return ans;


        // 桶排序
        int maxDist = Math.max(rCenter, rows - 1 - rCenter) + Math.max(cCenter, cols - 1 - cCenter);// 最大的距离
        List<List<int[]>> bucket = new ArrayList<List<int[]>>();
        for (int i = 0; i <= maxDist; i++) {
            bucket.add(new ArrayList<int[]>());
        } // 按照距离分桶，从最小距离的桶0到最大距离的桶maxDist;

        // 往桶里添加元素
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int d = dist(i, j, rCenter, cCenter);
                bucket.get(d).add(new int[]{i, j});
            }
        }
        int[][] ret = new int[rows * cols][];
        int index = 0;
        for (int i = 0; i < maxDist; i++) {
            for (int j = 0; j < bucket.get(i).size(); j++) {
                ret[index++] = bucket.get(i).get(j);
            }
        }
        return ret;
    }
    public int dist(int r1, int c1, int r2, int c2) {
        return Math.abs(r1 - r2) + Math.abs(c1 - c2);
    }
}
